package com.usts.edu.list;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * Created by Guanzhong Hu
 * Date :2019/12/27
 * Description :实现单链表
 * Version :1.0
 */
public class LinkList implements Ilist {

    private  Node head;

    public LinkList() {
        head = new Node();// 生成空的单链表
    }

//  置空
    @Override
    public void clear() {
        head.data = null;
        head.next = null;
    }

    @Override
    public boolean isEmpty() {
        return head.next==null; // 头指针为null，则空
    }

    @Override
    public int length() {
        int length = 0;// 初始化length
        Node n = head.next; // 初始化头指针，进行遍历
        while (n != null){
            n = n.next; // 迭代遍历
            length++;
        }
        return length;
    }

    @Override
    public Object get(int i) throws Exception {
        Node n = head.next;
        int flag = 0;// 初始化查找参数，依次遍历寻找，当存在下一个头指针且flag = i时，则返回当前指针指向的下一个元素
        while (n != null && i > flag){
            n = n.next;
            flag++;
        }
        if (n==null|| i<flag){
            throw  new Exception("查找的第"+i+"个元素不存在！");
        }
        return n.data;
    }

    @Override
    public void insert(int i, Object x) throws Exception {
        Node p = head;
        int flag = -1; // 定义计数器，从-1开始，因为第一个元素的头指针是-1；
        while (p!=null&&flag<i-1){ //寻找第i个结点的前驱，如果前驱小于则可以插入，否则当前元素位置已经占
            p = p.next;// 已经指向当前结点的位置，需要后期插入成功后，指向下一个结点位置
            flag++;
        }
        if (p==null&&flag>i-1) throw new Exception("插入位置不合法");
        Node newNode = new Node(x);
        newNode.next = p.next; // 指向下一个结点位置
        p.next = newNode;// 将当前生成的结点(下一个结点指针，当前节点元素)存入p的上一个结点的下一个结点的指针中
    }

    @Override
    public void remove(int i) throws Exception {
        Node p = head;
        int flag = -1; // 同上
        while (p!=null&&flag<i-1){
            p = p.next;
            flag ++;
        }
        if (p==null&&flag>i-1) throw new Exception("删除位置不合法");
        p.next = p.next.next;// 将此节点的上一个节点的指针指向当前删除节点的下一个结点
    }

    @Override
    public int indexOf(Object x) throws Exception {
        Node p = head;
        int flag = -1;
        while (p!=null&&p.data.equals(x)){
            p = p.next;
            flag ++;
        }
        if (p!=null) return flag;
        return -1;

    }

    @Override
    public void display() {
        Node p = head.next;
//        如果指针含有下一个元素，则输出，并替换查询指针
        while (p!=null){
            System.out.print(p.data);
            p = p.next;
        }
        System.out.println();
    }
    //创建链表,测试使用
    public void createLinkList(int len) throws Exception{ // 头插法，创建len长度的链表
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < len ; i++) {
            insert(0,scanner.next());
        }
    }
}
